#include <stdio.h>

//排序算法
//冒泡排序算法
void BubbleSort(int *a,int len)
{
    //冒泡n-1次
    for(int i = 0; i < len-1; i++)
    {
        int flag = 0;
        for(int j = 0; j < len-1-i; j++)
        {
            if(a[j] > a[j+1]) 
            {
                flag = 1;
                int temp = a[j];
                a[j] = a[j+1];
                a[j+1] = temp;
            }
        }
        //数列已经有序
        if(flag == 0)
        {
            break;
        }
    }
}

//插入排序
void InsertSort(int *a,int len)
{
    for(int i = 1; i < len; i++)
    {
        int temp = a[i]; 
        int j = i;
        for(; j > 0; j--)
        {
            if(a[j-1] > temp)
            {
                a[j] = a[j-1];
            }
            else
            {
                break;
            }
        }
        a[j] = temp;
    }
}

//选择排序：每次选择剩下数列中最小的一个数放到最前面
void ChooseSort(int *a,int len)
{
    for(int i = 0; i < len; i++)
    {
        int min = i;
        for(int j = i+1; j < len; j++)
        {
            if(a[j] < a[min])
            {
                min = j;
            }
        }
        int temp = a[i];
        a[i] = a[min];
        a[min] = temp;
    }
}

//选择排序的优化
void ChooseSort2(int *a,int len)
{
    int left = 0;
    int right = len-1;
    while(left < right)
    {
        int min = left;
        int max = right;
        for(int i = left; i <= right; i++)
        {
            if(a[i] < a[min])
            {
                min = i;
            }
            if(a[i] > a[max])
            {
                max = i;
            }
        }

        int temp = a[left];
        a[left] = a[min];
        a[min] = temp;
    
        if(max == left)
        {
            max = min;
        }

        temp = a[right];
        a[right] = a[max];
        a[max] = temp;

        left++;
        right--;
    }
}

void PrintArray(int *a,int len)
{
    for(int i = 0; i < len; i++)
    {
        printf("%d ",a[i]);
    }
    printf("\n");
}
int main()
{
    int a[] = {3,2,16,98,54,1,45};
    //BubbleSort(a,sizeof(a)/4);
    //InsertSort(a,sizeof(a)/4);
    ChooseSort2(a,sizeof(a)/4);
    PrintArray(a,sizeof(a)/4);

    return 0;
}